﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Queues;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Geometry.ConvexHull
{
    public class GrahamConvexHullFinder
    {
        public IEnumerable<Point2D> Find(IEnumerable<Point2D> points)
        {
            var pointsSeq = points.ToList();
            if (pointsSeq.Count < 3)
            {
                throw new ArgumentException("points must contains at least three or more points", "points");
            }
            var minY = pointsSeq.ArgMin(pt => pt.Y);
            var p = pointsSeq.Where(pt => pt.Equals(minY)).ArgMax(pt => pt.X);
            pointsSeq.Remove(p);
            pointsSeq.Sort((pt1, pt2) =>
            {
                var atanPt1 = Math.Atan2(p.Y - pt1.Y, p.X - pt1.X);
                var atanPt2 = Math.Atan2(p.Y - pt2.Y, p.X - pt2.X);
                if (atanPt1 == atanPt2)
                {
                    return pt1.X.CompareTo(pt2.X);
                }
                return atanPt1.CompareTo(atanPt2);
            });
            pointsSeq.Insert(0,p);
            Lifo<int> Q = new Lifo<int>();
            Q.Push(0); Q.Push(1);
            Q.Push(2);
            for(int i = 3; i < pointsSeq.Count; i++)
            {
                var j = Q[Q.Count - 1];
                var k = Q[Q.Count - 2];
                while ( !Utils.Left(pointsSeq[k],pointsSeq[j],pointsSeq[i]))
                {
                    Q.Pop();
                    j = Q[Q.Count - 1];
                    k = Q[Q.Count - 2];
                }
                Q.Push(i);
            }
            for(int i = 0; i < Q.Count; i++)
            {
                yield return pointsSeq[Q[i]];
            }
        }
    }
}
